As the number of new users of distributed networks increases, there is a greater demand that network services are provided with a high level of quality of service (QoS). Moreover, the volume of multimedia traffic (i.e., voice video, image, and data) increases due to these new users and associated applications, there is an increased demand to deliver these services with an acceptable QoS. However, as the traffic over the network increases, the QoS of the network decreases. Further straining the QoS of the network is that users also want to protect their investments in their existing IP-based desktops and Local Area Networks (LANs). This currently presents a problem as traditional Internet Protocol (IP) networks provide “best-effort” service. In the public IP-based Internet, it is difficult to provide differentiated QoS for either individual applications or for different types of multimedia traffic. This lack of native QoS support often results in reduced and unacceptable levels of QoS; e.g., Voice-over-IP services with delays of several seconds, and videoconferences with jerky, low-quality video. While this level of service quality may be acceptable for individual use, it is inadequate for business and military needs.
Another trend in distributed networks, which compounds the problem, is the proliferation of wireless applications for voice, fax, paging, data, images, and video. The use of these wireless applications is expanding to true global coverage through the use of satellite networks and in-flight data communications services on commercial airlines. These wireless networks generally have lower bandwidths and higher error-rates than traditional wired networks. However, mobile users still require the same QoS for their multimedia applications, whether they're at their desktop or in a tactical environment. Needless to say, mobility and wireless operation complicate the requirement of providing an acceptable end-to-end QoS.
One type of wireless network in particular, the “ad-hoc,” or Mobile Ad-Hoc Network (MANET) is particularly sensitive to these issues. MANETs are networks that may be deployed rapidly with little or no assistance and that do not have a central network structure, such as cellular-base stations or overhead satellite assets. The nodes within the MANETs are typically highly mobile and use a variety of wireless network platforms. Furthermore, nodes within the MANET may dynamically enter or leave the network. Therefore, the number of nodes and the disposition of nodes within the MANET are highly fluid and continually changing. By their nature, the MANET complicates the design and implementation of acceptable protocols to support communications between nodes within the network.
The configuration of an ad-hoc network can be either hierarchical or flat. In a hierarchical ad-hoc network, the network nodes are partitioned into groups called clusters. Within each cluster, one node is chosen to be a “cluster head.” Traffic between nodes that are in different clusters always involves the cluster heads of the source and destination clusters. Depending on the number of hierarchies, the network depth can vary from a single tier to multiple tiers. Additionally, only one “type” of equipment is necessary in flat networks, as all the nodes perform the same operation and there is no “single point of failure,” created by the cluster heads. Finally, the hierarchical networks require complex algorithms to maintain the tiers; e.g., creation and reconfiguration of the backbone network. The main advantage of a hierarchical ad-hoc network is the ease of the mobility management process. Cluster heads can act as databases that contain the “location” of the nodes in their own clusters. To determine the existence and the “location” of a mobile node, a query is broadcast to all the cluster heads. The appropriate cluster head then responds to the query originator. This relatively simple mobility management scheme can be mimicked in the flat networks by a routing algorithm. Finally, many network designers see hierarchical networks as matching the underlying hierarchical structure of the nodes, and their user's organization. This is especially true in military environments. However, one needs to separate the physical structure from the logical structure. Even if the underlying logical structure is indeed hierarchical, there is no reason why this logical structure cannot be implemented on top of a flat network-architecture.
In contrast, the nodes in a flat ad-hoc network are all equal. Connections are established between nodes that are in close enough proximity to one another to allow sufficient radio propagation conditions to establish connectivity. Routing between nodes is constrained by the connectivity conditions, and possibly by security limitations.
In the general case, a network may use a hybrid approach wherein a cluster-based topology is used for routing-control traffic but a flat network topology is used for the actual user-data traffic.
Ad hoc networking introduces several important difficulties for traditional routing protocols. First, determining a packet route requires that the source node know the reachability information of its neighbors. Second, the network topology may change quite often in an ad-hoc network. As the number of network nodes increases, the potential number of destinations becomes large, requiring large and frequent exchange of data (e.g., routes, routes updates, or routing tables) among the network nodes. Updates in the wireless communication environment travel over the air, and therefore consume a great deal of network resources. As the network size increases and as the nodal mobility increases, smaller and smaller fractions of this total amount of control traffic are of practical usefulness. This is due to the fact that as the nodes become more mobile, the lifetime of a link decreases, and the period in which the routing information remains valid decreases as well. It is easy to see that for any given network capacity, there exists a network size and nodal mobility for which all the network capacity is wasted on control traffic.
Existing IP routing protocols that manage wireless networks can be classified either as proactive or as reactive. Proactive protocols attempt to continuously evaluate the routes within the network, so that when a packet needs to be forwarded, the route is already known and can be used immediately. The family of Link-State protocols, such as OSPF, is one example of a proactive scheme, as is the family of Distance-Vector protocols, such as Routing Information Protocol (RIP). Reactive protocols, on the other hand, invoke a route determination procedure on demand only. Thus, when a route is needed, a global search procedure is employed. The classical flood-search algorithms are typical reactive protocols.
The advantage of the proactive protocols is that there is little delay involved in determining the appropriate route. In reactive protocols the delay to determine a route can be quite significant. Furthermore, the global search procedure of the reactive protocols requires significant control traffic. Because of this long delay and excessive control traffic, pure reactive routing protocols may not be applicable to real-time communication in MANETs. However, pure proactive schemes are also not appropriate for MANETs, as they continuously use a large portion of the network capacity to keep the routing information current. And, as mentioned above, most of this routing information is never used since ad-hoc network nodes often move quite fast.
A related issue is that of updates to the network topology database at each MANET node. For a routing protocol to be efficient, changes in the network topology must have local effect only. In other words, the creation of a new link at one end of the network is an important local event but, most probably, not a significant piece of information at the other end of the network. Proactive protocols tend to distribute such topological changes widely in the network, thereby incurring large costs. Furthermore, neither proactive nor reactive protocols employ a QoS routing.
An improvement to the protocols for ad-hoc networks uses both proactive and reactive protocols to create a hybrid routing protocol called Zone Routing Protocol (ZRP). ZRP, which is based on the notion of Routing Zones incurs very low overhead in determining a route from a source node to a destination node. The ZRP rapidly locates routes between nodes when transmission is necessary. The ZRP limits the scope of proactive routing to a local neighborhood around a particular node by defining a zone around each node in the network. The radius of the zone includes nodes whose distances from the particular node are equal to a predefined maximum number of hops. Thus, each node is only required to know the topography of the network within its zone radius. In spite of some networks being particularly large, topographical updates are only propagated locally. Therefore, route discovery in the proactive protocol is limited to only those nodes that lie within the zone radius. Additionally, the reactive protocol, which is used for inter zone connectivity, is limited to route discovery and to sending route queries to the nodes that lie at the boundary of the zone radius. In this manner, the queries hop across zone boundaries in distances of one zone radius, thereby limiting the overhead of the reactive protocol.
Although ZRP provides advantages over the proactive protocol and the reactive protocol, the ZRP has it limitations. Specifically, the ZRP does not include QoS in its route determination. When determining the route between the source node and the destination node, the ZRP will select the shortest route. That is, the ZRP will always select the route that has the fewest number of hops between the source node and the destination node. Although selecting the shortest route between nodes keeps the network overhead at a minimum, there is no consideration for the QoS of the route. There may be instances when the shortest route between nodes is not necessarily the “best” route. That is, a shorter route may sometimes be less stable than a longer route. Selecting a route that is less stable even though it may be the shortest route in the ad-hoc network can lead to delays and errors in communications between the nodes, which in most applications, such as battlefield conditions, is unacceptable.
For example, assume that the ad-hoc network is established for a military squad on a patrol mission in a battlefield environment. The source node is a squad commander and the destination node is the point man located 50 meters in front of the main squad. The shortest route between the squad commander and point man may be a single hop. However, battlefield conditions, such as intervening terrain, propagation effects, and the like, may cause the link between the squad commander and the point man to be degraded though still operational. An alternative route may exist between the company commander and the forward observer that includes an intervening node, such as a second member of the squad who is deployed on the squad's flank, in which there is a clear line-of-sight to both the squad commander and the point man. Thus, in this instance, the two-hop link between the commander and the point man will have better quality than the single-hop link. However, even though the two-hop link provides a higher quality signal than the single-hop link, the ZRP will select the single-hop link because it represents the shortest path between the commander and the point man. The ZRP protocol selects a network link based on the shortest route, regardless of whether a more robust link is available for a longer route fails to consider the QoS of the route.
Thus, there is a need in the art for a hybrid protocol that can be used with wireless ad-hoc networks that provides QoS routing within a hybrid routing protocol.